A digital circuit includes basic electronic circuits forming different digital components including logic gates, registers, etc. These digital components are interconnected to provide a circuit that operates in a desired fashion. A programmable logic array (PLA) has a plurality of such digital circuits that are mapped over logic elements to form an efficient and flexible device. An important objective during mapping an electrical circuit over a PLA is to map a maximum number of circuit elements over a single logic element, and to achieve a smallest possible network of logic elements to form the electrical circuit while insuring the minimum possible delay.
For mapping a digital circuit on a logic element the digital circuit is converted into a network of a plurality of interconnected nodes having termination nodes labeled as sources (s) and sinks (t). The nodes represent a generalized digital component of the digital circuit. Two nodes are interconnected by at least an edge. Each edge is assigned a capacity Cij that represents the amount of flow through the edge. The capacity Cij represents capacity of the edge connecting ith node to jth node.
Further, a residual network can be produced by introducing a residual edge between two interconnected nodes in the original network. The residual capacity of the residual edge can then be defined as an amount of additional net flow that can be pushed across two nodes without exceeding the capacity Cij of the edge connecting these nodes in the original network. The network is then mapped over the logic element using a logic algorithm.
An augmenting path algorithm is one of the commonly used algorithms to find all distinct paths in the network. According to the algorithm, an augmented path is a directed path from the source to the sink in the residual network such that every arc on this path has a strictly positive residual capacity. The minimum of these residual capacities is called the residual capacity of the augmenting path because it represents the amount of flow that can feasibly be added to the entire path. A mathematical derivation, proof and examples of the augmenting path algorithm are available in general textbooks/research papers relating to the subject matter.
Various technologies propose different methods for mapping a digital circuit on a logic element. For example, a polynomial time technology mapping algorithm has been proposed by Chen et. al., “Flow-map: An Optimal Technology Mapping Algorithm For Delay Optimization In Lookup-Table Based FPGA Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems CAD, vol. 13, pp. 1–12, January 1994, in which a Flow-Map optimally maps electrical circuits on a FPGA for depth minimization by computing a minimum height for k-feasible cut a network. This algorithm is commonly used for technology mapping.
In another research article by Cong et. al., “On Area/Depth Trade-off In LUT-Based FPGA Technology Mapping,” in 30th ACM/IEEE Design Automation Conference (DAC), pp. 213–218, 1993, an algorithm for FPGA mapping technology is disclosed. In this technique a number of depth relaxation operations are performed to obtain a new network with bounded increases in depth. This is advantageous to a subsequent re-mapping for area minimization by gradually increasing depth.
An integrated approach for synthesizing and mapping has been disclosed by Cong et al., “Beyond The Combinatorial Limit In Depth Minimization For LUT-Based FPGA Designs,” in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 110–114, November 1993. This algorithm uses global combinatorial optimization techniques to guide the Boolean synthesis process during depth minimization. The combinatorial optimization is achieved by computing a series of minimum cuts of fixed heights in a network based on fast network computation, and the Boolean optimization is achieved by efficient ordered binary decision diagrams (OBDD) based upon implementation of functional decompositions.
Further, in an approach by Francis et. al. “Chortle: A Technology Mapping Program For Lookup Table-Based Field Programmable Gate Arrays,” Proc. 27th ACM/IEEE Design Automation Conference, pp. 613–619, June 1990, a new algorithm has been discussed for technology mapping in which the method for choosing gate level decompositions based on bin packing is innovative.
Several other approaches have also been applied to achieve these objectives. However, all the methods mentioned above and many others either map a minimum number of logic elements or minimize a delay of the mapped circuit. There is no method that maps a design such that delay of the mapped circuit is minimum and the area is minimum under the delay.
Thus, it has been observed that there is a need to develop a technique that provides a method and device for packing a maximum number nodes in a single logic element while ensuring minimum delay.